package com.darrenchan.leetcode;

import java.util.Arrays;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-05 12:15
 */
public class Q55 {
    //    public boolean canJump(int[] nums) {
//        if (nums == null || nums.length == 0) {
//            return false;
//        }
//        if (nums.length == 1) {
//            return true;
//        }
//
//        int len = nums.length;
//        boolean[] dp = new boolean[len];
//
//        for (int i = len - 2; i >= 0; i--) {
//            dp[i] = len - 1 - i <= nums[i];
//            if (!dp[i]) {
//                for (int j = i + 1; j < len; j++) {
//                    if (dp[j] && j - i <= nums[i]) {
//                        dp[i] = true;
//                        break;
//                    }
//                }
//            }
//        }
//        return dp[0];
//    }
//
//    public static void main(String[] args) {
//        System.out.println(new Q55().canJump(new int[]{1, 2, 3}));
//    }
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if(dp[j] && nums[j] >= i - j){
                    dp[i] = true;
                }
            }
        }
        return dp[nums.length - 1];
    }

}
